package tree.路径总和III;


import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
        prefix.put(0L, 1);
        return dfs(root, 0L, prefix, targetSum);
    }

    public int dfs(TreeNode node, Long curPrevSum, Map<Long, Integer> prefix, int targetSum) {
        if (node == null) {
            return 0;
        }
        curPrevSum += node.val;
        int ans = prefix.getOrDefault(curPrevSum - targetSum, 0);
        prefix.put(curPrevSum, prefix.getOrDefault(curPrevSum, 0) + 1);
        ans += dfs(node.left, curPrevSum, prefix, targetSum);
        ans += dfs(node.right, curPrevSum, prefix, targetSum);
        prefix.put(curPrevSum, prefix.getOrDefault(curPrevSum, 0) - 1);
        return ans;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int i = solution.pathSum(new TreeNode(1000000000, new TreeNode(1000000000, new TreeNode(294967296, new TreeNode(1000000000, new TreeNode(1000000000, new TreeNode(1000000000), null), null), null), null), null), 1000000000);
        System.out.println(i);
        System.out.println(Integer.MIN_VALUE);
        System.out.println(-2000000000L - 294967296L);
    }
}
